The demand for improved security and privacy has led to the incorporation of cryptographic engines in a wide range of communication systems and data processing systems. Many of these cryptographic engines use public key cryptography algorithms (RSA, DSA, El-Gamal) that rely on modular arithmetic to crypt/decrypt messages. The basic operation used in these algorithms is a modular multiplication, which computes R=AB mod N, where A, B and N are large numbers, typically with hundreds of digits.
Implementation of this basic operation has been made quite efficient thanks to Montgomery's theorem, which provides a multiplication technique for computing R without a long division by N to obtain the remainder. Practical implementations of Montgomery multiplication decompose A into k blocks of p bits to limit the size of the intermediate numbers (i.e., there is no need to store the product AB explicitly).
FIG. 1 illustrates prior art cryptographic engine 110, which is based on Montgomery multipliers. Cryptographic engine 110 receives the parallel input Ai and the serial inputs B[j] and N[j] and produces the serial output (or result) R[j]. The parallel input Ai is stored in register 115 in cryptographic engine 110. It is assumed that N is an odd integer and that both A and B are integers smaller than N. The sizes of A, B and N are on the order of several hundred bits.
Most common implementations that compute R=AB mod N are based on the Montgomery's interleaved multiplication. The input data A, B, S and N enter cryptographic engine in a serial fashion (one or more bit at each cycle). The output data, R, is obtained serially. The following equations summaries the basic operations carried by Montgomery-based cryptographic engine 110:T=S+(Ai·B)  [Eqn. 1]Y=(T·J)mod 2p  [Eqn. 2]R=(T+N·Y)/2p  [Eqn. 3]where J is a p-bit constant, such that J·N0=−1 mod 2p, and Ai is the ith block of p bits of A. The number p is usually a power of 2, such as 32 or 64. The numbers J and Y are stored internally in the registers of cryptographic engine 110. The final result A.B mod N is obtained by iterating the Equation 1, 2 and 3 over each block of p bit of A with the number S of the current iteration being equal to the number R of the previous iteration. Initially, S is zero.
However, cryptographic engines are often the prime targets of hacker attacks in which hostile parties attempts to discover the secret encryption keys. These attacks may take a number of forms, including invasive (e.g., physical probing), non-invasive (e.g., current probing), and disruptive (e.g., fault injection). Cryptographic researchers have extensively studied these types of attacks extensively and have added a number of hardware and software countermeasures to conventional cryptographic engines to minimize the impact of such attacks.
Disruptive attacks are of particular concern. Disruptive attacks inject a fault (e.g., sudden voltage drop) during cryptographic computations and these faults may corrupt the computation results. Unfortunately, in the current state-of-the-art cryptographic devices, it is impossible to verify whether or not the computation engine returns correct result for S.
Therefore, there is a need in the art for an improved cryptographic engine. In particular, there is a need for an apparatus and method for verifying the results from a cryptographic engine that may be subject to a disruptive attack.